// LeetCode 1743
// 存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
// 给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
// 题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，
// 也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
// 返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


// 用哈希表记录每个数相邻的数，只有一个的即为数组开头

package leetcode

func restoreArray(adjacentPairs [][]int) []int {

	// 统计入参中所有相邻的数
	pairMap := map[int][]int{}
	for _, pairs := range adjacentPairs {
		v := pairs[0]
		w := pairs[1]
		pairMap[v] = append(pairMap[v], w)
		pairMap[w] = append(pairMap[w], v)
	}

	// 找出开头/结尾
	startNum := 0
	for i, pair := range pairMap {
		if len(pair) == 1 {
			startNum = i
			break
		}
	}

	// 构造返回值
	ln := len(adjacentPairs) + 1
	ans := make([]int, ln)
	ans[0] = startNum
	ans[1] = pairMap[startNum][0]

	for i := 2; i < ln; i ++ {
		if pairMap[ans[i - 1]][0] == ans[i - 2] {
			ans[i] = pairMap[ans[i - 1]][1]
		} else {
			ans[i] = pairMap[ans[i - 1]][0]
		}
	}

	return ans



}
